//https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
package codeRandomThoughts.Test19删除链表中的倒数第N个结点;

import codeRandomThoughts.utils.ListNode;

public class Solution {

    //用了两趟扫描才实现
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode curr = dummyHead;
        int length = 0;
        while (curr.next != null) {
            curr = curr.next;
            length++;
        }

        //把倒数转化为正数
        int index = length - n + 1;
        //重新遍历,要遍历到删除节点的前一项
        curr = dummyHead;
        for (int i = 0; i < index - 1; i++) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        return dummyHead.next;
    }

    /**
     * 尝试用1趟扫描实现?
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;

        //快指针比慢指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        if (fast == null) {
            return head.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}
